package com.atwy.sort;

/**
 * 希尔排序，是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
 * 说明插入排序的缺点：插入排序是将无序队列元素与有序队列从后往前进行比较，然后将大的数进行后移，最后将无序元素插入。
 * 如果插入的无序元素很小时，后移的次数就会增加，对效率也就会有影响
 * <p>
 * 我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，
 * 这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。
 * <p>
 * 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
 * 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 2.按增量序列个数k，对序列进行k 趟排序；
 * 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
 * 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class ShellSorting {
    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));




    }

    /**
     * 希尔排序也是一种插入排序，所以先理解插入排序
     * 插入排序是将待排序队列分为有序队列和无序队列，
     * 一般是将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
     * <p>
     * 希尔排序先将队列进行分组，共gap组，然后再对每组进行插入排序，
     * 那么每组的第一个元素就是 0 - (gap-1),这里是数组下标，其中0是第一组的第一个元素，gap-1是gap组的第一个元素，
     * gap下标就是第一组的第二个元素，gap下标是要和0下标的元素进行比较的。
     * <p>
     * 所以算法上，第一层循环是对队列进行分组
     * 第二层循环是 从各组的第二个元素开始遍历（默认各组的第一个元素是有序的），各组的比较是交叉进行的
     * <p>
     * 第三层循环是，从无序队列取出元素，从后向前遍历有序队列进行比较
     *
     * @param array
     */
    public static void sort(int[] array) {
        int temp, index;

        for (int gap = array.length / 2; gap > 0; gap /= 2) {

            for (int i = gap; i < array.length; i++) {
                // 遍历各组中所有的元素，共gap组,每组 array/gap个元素，步长是gap
                temp = array[i];
                index = i;
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 比较各组元素,大的往后移
                    if (temp < array[j]) {
                        array[j + gap] = array[j];
                        index = j;
                    } else {
                        break;
                    }

                }
                if (index != i) {
                    array[index] = temp;
                }
            }

        }
    }


}

